ece6605-2023-10-12-Privacy amplification.tmpMMgSok

Announcements

Assignment 1 and 2
- Solutions posted on Canvas
- Grading takes a lot of time… sorry, but I'm hoping to wrap up tonight
Assignment 3
- Coming up
Midterm
- Tuesday October 17, 2023
- In class, with notes (no electronic notes)
- Covering Homework 1 & 2
- Office hours on Friday October 13, 2023 11am
- Office hours on Monday October 16, 2023 11am
Last time
- A cool new result: Privacy amplification
Today
- More Privacy amplification
- Glimpse of information theory and security
- Applications to random number generation

Ultrafast random number generation

Ido Kanter et al., An optical ultrafast random bit generator, Nature Photonics, (2010)
- The generation of random bit sequences based on non-deterministic physical mechanisms is of paramount importance for cryptography and secure communications.
- We present a physical random bit generator, based on a chaotic semiconductor laser, having time-delayed self-feedback, which operates reliably at rates up to 300 Gbit/s.
- The randomness of long bit strings is verified by standard statistical tests.
Chaotic laser intensity fluctuations digitized at a 20 GHz sampling rate with an 8-bit resolution
- How much true randomness can we generate?

Privacy amplification

A $(n, K_{n})$ code $C$ for privacy amplification coding a discrete memoryless source $p_{X}$ against side information $Z$ consists of an encoding function $f_{n} : X^{n} \to {1; K_{n}}$ .

The performance of an $(n, K_{n})$ code is measured in terms of
1. The rate of the code $R ≜ \frac{\log_{2} K_{n}}{n}$ (bits/source symbol)
2. The secrecy and uniformity of $M$ measured as
  
  $\begin{array}{r} S^{(n)} (C) ≜ V (P_{M Z^{n}}, Q_{M} \cdot P_{Z}^{\otimes n}) \end{array}$
  
  where $Q_{M}$ is the uniform distribution on ${1; K_{n}}$

Privacy amplification

Define again $C_{pa} ≜ sup {R : \exists {f_{n}}_{n \geq 1} with lim_{n \to \infty} \frac{\log K_{n}}{n} \geq R and lim_{n \to \infty} S^{(n)} = 0}$

For a discrete memoryless source $P_{X Z}$ , $C_{pa} = H (X | Z)$

Achievability

Consider a generic source $(V, P_{V})$ and a generic channel $(V, P_{U | V}, U)$ with $| U | < \infty$ .
For $γ > 0$ , let

$\begin{array}{r} D_{γ} = {(u, v) \in U \times V : \log \frac{1}{P_{U | V} (u | v)} > γ} . \end{array}$
For each $u \in U$ , let $f (u)$ be a bin index drawn independently with uniform distribution on $[1; K]$ .
Define an encoder as the mapping $u \to f (u)$ .

For any $γ > 0$ ,

$\begin{array}{r} E_{} [V (P_{V M}, P_{V} Q_{K} M] \leq P_{P_{V} P_{U | V}} ((U, V) \notin D_{γ}) + \frac{1}{2} \sqrt{\frac{K}{2^{γ}}} . \end{array}$

Converse

Consider a sequence of codes ${f_{n}}_{n \geq 1}$ such that $lim_{n \to \infty} S^{(n)} = 0$ and $lim_{n \to \infty} \frac{\log K_{n}}{n} \geq R$ . Then $R \geq H (X | Z)$

We shall use a supporting lemma

For $P, Q \in Δ (X)$ , we have $| H (P) - H (Q) | \leq V (P, Q) \log \frac{| X |}{V (P, Q)}$

ECE 6605 - Information Theory